package com.xgh.middle;

/**
 * @ClassName Test92
 * @Description
 * @Author xinggh
 * @Date 2020/7/30 23:43
 * @Version 1.0
 **/
public class Test215 {

    /**
     * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     * <p>
     * 示例 1:
     * <p>
     * 输入: [3,2,1,5,6,4] 和 k = 2
     * 输出: 5
     * 示例 2:
     * <p>
     * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
     * 输出: 4
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        int i = quickSort(nums, 0, nums.length - 1, nums.length - k + 1);
        return nums[i];
    }

    int part(int[] nums, int low, int high) {
        int key = nums[low];
        int i = low;
        int j = high;
        while (i < j) {
            if (i < j && nums[j] >= key) {
                j--;
            }
            nums[i] = nums[j];
            if (i < j && nums[i] <= key) {
                i++;
            }
            nums[j] = nums[i];

        }
        nums[i] = key;
        return i;
    }

    int quickSort(int[] nums, int low, int high, int k) {
        if (low >= high) {

        }
        int part = part(nums, low, high);
        quickSort(nums, low, part - 1, k);
        quickSort(nums, part + 1, high, k);
        System.out.println("part" + part);
        /*if (part == k) {
            return part;
        }
        if (part > k) {
            part = quickSort(nums, low, part - 1, k);
        } else {
            part = quickSort(nums, part + 1, high, k);
        }
*/
        return part;
    }


    public static void main(String[] args) {
        int arr[] = {3, 2, 1, 5, 6, 4};
        Test215 test215 = new Test215();
        int kthLargest = test215.findKthLargest(arr, 2);
        System.out.println(arr);
        System.out.println(kthLargest);
    }
}
